With increasing progress and popularity of network communications and e-commerce in recent years, it has become very important to achieve high security. One method to achieve high security is to use encryption in communication, and many encryption techniques are known.
For example, there is a known system in which a cryptographic processing module is disposed in a small-sized apparatus such as an IC card whereby, when data is transmitted between the IC card and a data reader/writer, processing including authentication and encryption/decryption of data is performed.
IC cards having a capability of performing cryptographic processing are widely used. For example, such IC cards are used to pass through entrance gates of stations, to perform payment in shopping centers, etc. In many applications of IC cards, there is an increasing demand for reduction in size and increase in processing speed.
Cryptography methods are categorized into two types: common key cryptography and public key cryptography. The common key cryptography is also called symmetric key cryptography. In the common key cryptography, a sender and a receiver both have a common key. A specific example of a common key cryptography technique is that using a DES (Data Encryption Standard) algorithm. In the DES algorithm, encryption and decryption can be accomplished in substantially the same manner.
In the public key cryptography (also called asymmetric key cryptography), in contrast to the common key cryptography, different keys are used by a sender and a receiver. Compared with the common key cryptography in which a common key is used in both encryption and decryption, the public key cryptography is advantageous in that only one specific person needs to have a secret key which must be kept secret and thus it is easy to manage the secret key. However, the public key cryptography is low in processing speed compared with the common key cryptography. Because of the low processing speed, the public key cryptography is generally used in applications which deal with only small data size, such as transmission of a secret key, digital signature, etc. Specific examples of public-key cryptography is RSA (Rivest-Shamir-Adleman) cryptography and ECC (Elliptic Curve Cryptography).
In the elliptic curve cryptography, encryption is performed using an elliptic curve y2=x3+ax+b (4a3+27b2≠0) on a prime field or an elliptic curve y2+xy=x3+ax2+b (b≠0) on an extension field of 2. If a point (O) at infinity is added to a set of points on such a curve, the resultant set forms a finite group with respect to addition, and the point (O) at infinity is an element of the finite group. The operation of addition over the finite group is denoted by +. Addition of two points P and Q on the finite group, that is, P+Q, is referred to as “addition of points”, and addition of point P and point P, P+P=2P, is referred to as “doubling of a point”. An operation of repeatedly adding of point P k times such that P+P+ . . . +P=kP is referred to as “scalar multiplication of a point”.
It is known that scalar multiplication of a point can be accomplished by addition of points and doubling of a point. Details of addition, doubling, and scalar multiplication of points on an elliptic curve over a prime field or points on an elliptic curve over an extension field of degree 2 in an affine coordinate system (x, y) or a projective coordinate system (X, Y, Z) are described in IEEE P1363/D13 Standard Specifications for Public Key Cryptography.
Koblitz and Cantor have proposed hyperelliptic curve cryptography (HECC) which is generalization of the elliptic curve cryptography. Descriptions of the hyperelliptic curve cryptography can be found, for example, in Non-Patent Document 1 and Non-Patent Document 2.
In the elliptic curve cryptography, when a point P on an elliptic curve defined over a finite field Fq is given, if a point Q=kP (kεZ), that is, a point obtained by multiplying point P by a scalar k is further given, it is known that a problem of finding k for the given point Q reduces to a discrete logarithm problem. On the other hand, in the case of public key cryptography based on the hyperelliptic curve cryptography, when a divisor D1 which is a formal sum of points and a divisor D2 obtained by multiplying D1 by a scalar k are given, a problem of finding k from D2 reduces to a discrete logarithm problem on a Jacobian variety of a hyperelliptic curve.
A hyperelliptic curve is characterized by a genus g. When q=pn where p is a prime and n is a positive integer, a hyperelliptic curve C of genus g defined over a finite field Fq is defined by the following equation:y2+h(x)y=f(x)where h(x), f(x)εFq[x], and f(x) is a monic polynomial of degree 2g+1.
A point −P opposite to the point P=(x, y) on the hyperelliptic curve C is defined by (x, y+h(x)). When P=−P, this point P is called a ramification point.
It is known that in the hyperelliptic curve cryptography, a security level comparable to that obtained by the elliptic curve cryptography can be achieved by a field of definition of a hyperelliptic curve with a processing size which is 1/g times that of the elliptic curve. This small processing size provides a great merit in implementation of the hyperelliptic curve cryptography, which is one of the advantages of the hyperelliptic curve cryptography.
Fundamental matters of the hyperelliptic curve cryptography are explained. In the hyperelliptic curve cryptography, as described above, when a divisor D1 which is a formal sum of points and a divisor D2 obtained by multiplying D1 by a scalar k are given, a problem of finding k from D2 reduces to a discrete logarithm problem on a Jacobian variety of a hyperelliptic curve, and this problem can be applied to public key cryptography.
The divisors can be expressed in the following form:
[Mathematic Expression 1]
  D  =                                                                        ∑                i                            ⁢                                                          ⁢                                                m                  i                                ⁢                                  P                  i                                                      -                                          (                                                      ∑                    i                                    ⁢                                                                          ⁢                                      m                    i                                                  )                            ⁢                              P                ∞                                              ,                                                  m            i                    ≥          0                    
In the above expression, Pi=(xi, yi), and Pi≠Pj when i≠j. The divisor in this form is called a semi reduced divisor.
Σmi is referred to as a weight of D. When the weight of a semi reduced divisor is equal to or smaller than the genus g, the semi reduced divisor is called a reduced divisor.
An arbitrary semi reduced divisor D on a Jacobian variety of a hyperelliptic curve can be expressed in a Mumford form D=(U, V) using the following polynomials U and V (U, VεFq[x]). A further detailed description of the Mumford expression may be found, for example, in Non-Patent Document 3.U=Π(x−xi)mi V(xi)=yi V(x)2+V(x)h(x)−f(x)≡0 mod U(x),deg V<deg U  [Mathematic Expression 2]
An arbitrary reduced divisor D of genus 2 can be expressed in the Mumford form using a set of polynomials of degree 2 or less whose coefficients are elements of the finite field Fq, as follows:(U,V)=(x2+u1x+u0,v1x+v0)
An arbitrary reduced divisor D of genus 3 can be expressed in the Mumford form using a set of polynomials of degree 3 or less whose coefficients are elements of the finite field Fq, as follows:(U,V)=(x3+u2x2+u1x+u0,v2x2+v1x+v0)
In the following description, it is assumed that the divisor D is a reduced divisor unless otherwise specified. Note that, as described above, the reduced divisor is a semi reduced divisor with a weight equal to or smaller than genus g.
Of reduced divisors, those other than a divisor with a weight equal to genus g, that is, reduced divisors having a weight smaller than genus g, are called degenerate divisors.
For example,
when genus g=2, degenerate divisors are divisors with a weight equal to 1, and
when genus g=3, degenerate divisors are divisors with a weight equal to 1 or 2.
For genus g=2 and for genus g=3, respectively, degenerate divisors can be represented using the Mumford expresses as follows:
(a) degenerate divisors of genus 2 (weight of 1): (U, V)=(x+u, v)
(b) degenerate divisors of genus 3 (weight of 1): (U, V)=(x+u0, v0)
(c) degenerate divisors of genus 3 (weight of 2): (U, V)=(x2+u1x+u0, v1x+v0)
Scalar multiplication of a divisor used in the hyperelliptic curve cryptography is explained below. Scalar multiplication of a divisor can be accomplished by a combination of addition of divisors and doubling of the divisor. This algorithm is called an addition algorithm. Some examples of addition algorithms are explained below.
A first proposed practical algorithm is known as a Cantor algorithm. A detailed description of the Cantor algorithm may be found, for example, in Non-Patent Documents 1 and 2. This Cantor algorithm is applicable to a divisor on a hyperelliptic curve of any genus. However, the Cantor algorithm has a disadvantage that, compared with an elliptic curve, the Cantor algorithm is complicated and needs a great amount of calculation.
Harley has proposed an algorithm in which hyperelliptic curves are limited to those of genus 2, and calculation is performed differently in an optimized manner depending on the weight of divisors thereby minimizing the amount of calculation. The proposal of this algorithm by Harley has stimulated further research on the calculation algorithm of the hyperelliptic curve cryptography (HECC) to achieve further improvement or extension.
In the Harley algorithm, a prime field is given as the field of definition, the curve is of genus=2, and divisors are expressed in the Mumford form. Examples of improvements in terms of the amount of calculation of the algorithm may be found, for example, in Non-Patent Document 4, Non-Patent Document 5, and Non-Patent Document 6. Examples of an algorithm extended to the case where an extension field of degree of 2 is given as the field of definition may be found, for example, in Non-Patent Document 7 and Non-Patent Document 8. Examples of extension of the Harley algorithm to genus 3 may be found, for example, in Non-Patent Document 9 and Non-Patent Document 10. Examples of reducing the amount of calculation by expressing divisors in the extended Mumford expression or using the weighted coordinates may be found, for example, in Non-Patent Document 11, Non-Patent Document 12, Non-Patent Document 6, and Non-Patent Document 13.
The Harley algorithm is explained below with reference to FIGS. 1 and 2. FIG. 1(A) shows an example of a process of addition D1+D2 for the case of genus 2. In this example, it is assumed that divisors D1 and D2 are respectively given as D1=(U1, V1) and D2=(U2, V2). First, a calculation mode is selected depending on the weight of divisors. More specifically, one of calculation modes is selected depending on the weights of the respective divisors D1 and D2 as follows.
(1) weight=2 for D1, weight=2 for D2 
(2) weight=2 for D1, weight=1 for D2
(3) exception handling 1
In the case where divisors with weight=2 are added together, that is, in the case of (1) weight=2 for D1 and weight=2 for D2, if the greatest common divisor gcd(U1, U2)=1 for the divisors D1=(U1, V1) and D2=(U2, V2), the two divisors D1=(U1, V1) and D2=(U2, V2) include neither a common point nor opposite points. In this case, addition is performed according to the Harley algorithm. This addition process is denoted as follows:
(1a) HarleyADD
In the technique disclosed in Non-Patent Document 7, this process (1a) HarleyADD is called a Most-Frequent-Case process, because this process is performed most frequently in the addition of D1+D2 for the case of genus of 2.
A specific process of HarleyADD performed as the Most-Frequent-Case process for genus 2 is shown below in [Table 1].
[Mathematic Expression 3]
TABLE 1HarleyADD(genus 2)Input: D1 = (u1, v1), deg u1 = 2, D2 = (u2, v2), deg u2 = 2Output: D3 = (u3, v3) = D1 + D21Compute r = res(u1, u2):4Mw1   u11 + u21, w0    u21w1 + u10 + u20, r   (u10 + u20)w0 + u20w12,2Compute I = i1x + i0 ≡ ru1−1 mod u2i1    w1, i0   w0;3Compute T = t1x + t0 ≡ (v1 + v2)I mod u2:5Mt2    (v11 + v21)w1, t0    (v10 + v20)w0,t1    (v11 + v21 + v10 + v20)(w0 + w1) + t2 + t0,t1    t1 + t2u21, t0    t0 + t2u20;4If t1 = 0 then call exceptional procedure.5Compute S = s1x + s0:1I + 6Mw2    (rt1)−1, w3    w2r, w4    w2t1, w5    w3r, s1    w4t1, s0    w4t0;6Compute u3 = x2 + u31x + u30 = s1−2(f + h(Su1 + v1) + (Su1 + v1)2)/u1u2:5Mu31    w1 + w5(1 + w5), u30    u21w1 + u10 + u20 + w5(s0 + s02 + w1);7Compute v3 + v31x + v30 ≡ Su1 + v1 + h mod u3:5Mw1    u11 + u31, w0    u10 + u30, w2    s1w1, w3    s0w0,w4    (s1 + s0)(w1 + w0) + w2 + w3, w2    w2 + 1, w1    w4 + w2u31,w0    w3 + w2u30, v31    w1 + v11 + h1, v30    w0 + v10 + h0;totalHarleyADD 1I + 25M
The probability of occurrence of the process of (1a) HarleyADD is very high, while the probability of occurrence of exception handling is very low. In the case where the condition of the Most Frequent Case is not satisfied that is, in the case where the greatest common divisor gcd(U1, U2)≠1 for the divisors D1=(U1, V1) and D2=(U2, V2), exception handling is performed. The exception handling process performed in this case is denoted as follows:
(1b) Exception Handling 2
In the case of (2) weight=2 for D1 and weight=1 for D2, determination is made as to whether gcd(U1, U2)=1. If it is determined that gcd(U1, U2)=1, then the following process is performed.
(2a) ExHarADD2+1→2 
However, if it is determined that gcd(U1, U2)≠1, then the following exception handling is performed.
(2b) Exception Handling 3
The algorithm of (2a) ExHarADD2+1→2 is described in Non-Patent Document 8. A specific process of ExHarADD2+1→2 is shown below in [Table 3].
[Mathematic Expression 4]
TABLE 3ExHarADD2+1→2 (genus 2)Input: D1 = (u1, v1), deg u1 = 1, D2 = (u2, v2), deg u2 = 2Output: D3 = (u3, v3) = D1 + D21Compute r ≡ u2 mod u11Mr    u20 + (u21 + u10)u10.2Compute inverse of u2 mod u1:1Iinv    1/r.3Compute s0 = inv(v1 + v2) mod u1:2Ms0    inv(v10 + v20 + v21v10).4Compute l = s - u2 = s0x2 + l1x + l0:2Ml1    s0u21: l0    s0u20.5Compute k = (f + v2h + v22)/u2 = x3 + k2x2 + k1x + k0:1Mk2    f4 + u21, k1    f3 + (f4 + u21)u21 + v21 + u20.6Compute u3 = (k + s(l + h))/u1 = x2 + u31x + u30:3Mu31    k2 + s02 + s0 + u10,u30    k1 + s0(l1 + h1) + u10u31.7Compute v3 = v31x + v30 ≡ (l + v2) + h mod u3:2Mv31    u31(h2 + s0) + (h1 + l1 + v21),v30    u30(h2 + s0) + (h0 + l0 + v20).totalExHarADD2+1→21I + 11M
(3) If it is determined that the weights satisfy neither (1) nor (2), then the exception process (3) is performed.
FIG. 1(B) shows an example of a doubling operation process for genus=2. The doubling operation is an operation to determine D+D=2D. The doubling operation is performed in a different mode depending on which one of values described below is assigned to the weight of the divisor D.
(4) weight=2
(5) weight=1
(6) weight=0
(4) When weight=2, it is checked whether the divisor includes a ramification point. If it is determined that the divisor includes no ramification point, then (4a) HarleyDBL is performed. On the other hand, if the divisor includes a ramification point, then (4b) exception process 6 is performed.
In Non-Patent Document 7, it is described that the process (4a) HarleyDBL occurs most frequently. A specific process of HarleyDBL is shown below in [Table 2].
[Mathematic Expression 5]
TABLE 2HarleyDBL(genus 2)Input: D1 = (u1, v1), deg u1 = 2Output: D3 = (u3, v3) = 2D11Compute r = res(u1, h):4Mw1    h1 + u11, w0    h0 + u10 + u11w11, r    u10(u10 + h0 + h1w1) + h0w0;2Compute I = i1x + i0 ≡ rh−1 mod u1i1    w1, i0    w0;3Compute T = t1x + t0 ≡ I(f + hv1 + v12)/u1 mod u1:8Mw2    f3 + v11 + u112, w3    v10 + v11(v11 + h1),t1    w0w2 + w1w3, t0    (u11w0 + u10w1)w2 + w0w3;4If t1 = 0 then call exceptional procedure.5Compute S = s1x + s0:1I + 6Mw0    (rt1)−1, w2    w0r, w3    w0t1, w4    w2r, s1    w3t1, s0    w3t0;6Compute u3 = x2 + u31x + u30 = s1−2(f + h(Su1 + v1) + (Su1 + v1)2)/u12:4Mu31    w4(1 + w4), u30    w4(w4(s0(1 + s0)) + w1);7Compute v3 = v31x + v30 ≡ Su1 + v1 + h mod u3:5Mw1    u11 + u31, w0    u10 + u30, w2    s1w1, w3    s0w0,w4    (s1 + s0)(w1 + w0) + w2 + w3, w2    w2 + 1, w1    w4 + w2u31,w0    w3 + w2u30, v31    w1 + v11 + h1, v30    w0 + v10 + h0;totalHarleyDBL 1I + 27M
The addition operation and the doubling operation for genus=3 are described below with reference to FIG. 2. The basic idea of the process for genus=2 can be applied to the case of genus=3. However, in the case of genus=3, the weight of the divisor can be up to 3, and thus there are much greater number of modes than in the case of genus=2.
In the addition operation shown in FIG. 2(A), when divisors D1=(U1, V1) and D2=(U2, V2) are given, an operation mode is selected depending on the weights of the divisors. More specifically, the operation mode is determined depending on the weights of the respective divisors D1 and D2 as follows.
(1) weight=3 for D1, weight=3 for D2 
(2) weight=3 for D1, weight=2 for D2 
(3) weight=3 for D1, weight=1 for D2 
(4) Exception Process 7
In the case of (1) weight=3 for D1 and weight=3 for D2, if the greatest common divisor gcd(U1, U2)=1 for the divisors D1=(U1, V1) and D2=(U2, V2), then the following operation is performed.
(1a) HarleyADD
This operation occurs most frequently in the addition operation for genus=3.
A further detailed description of the operation of HarleyADD, which is a most-frequent-case operation in the addition operation for genus=3, can be found, for example, in Non-Patent Document 9 and Non-Patent Document 10. An algorithm of HarleyADD, which is a most-frequent-case operation in the addition operation for genus=3, is shown below in [Table 4].
[Mathematic Expression 6]
TABLE 4HarleyADD(genus 3)Input: D1 = (u1, v1), deg u1 = 3, D2 = (u2, v2), deg u2 = 3Output: D3 = (u3, v3) = D1 + D21Compute r = res(u1, u2):14M 2Compute almost, inverse inv ≡ r/u1 mod u2:4M3Compute s′ = rs ≡ inv(v1 + v2) mod u2:11M 4Compute s = (s′/r) and make s monic:1I + 8M5Compute z = su1:6M6Compute u3 = (s(z + w4h) − w5(f + hv1 + v1)/u1)/u2:16M 7Compute v3 = −(w3z + h + v1) mod u3:8M8Compute u3 = (f + hv + v2)/u3:8M9Compute v3 = v32x2 + v31x + v30 ≡ v3 + h mod u3:3MtotalHarleyADD 1I + 78M
In the case of (2) weight=3 for D1 and weight=2 for D2, if the greatest common divisor gcd(U1, U2)=1 for the divisors D1=(U1, V1) and D2=(U2, V2), then the following operation is performed.
(2a) ExHarADD3+2→3 
if the greatest common divisor gcd(U1, U2)≠1, then the following exception handling is performed.
(2b) Exception Handling 9
In the case of (3) weight=3 for D1 and weight=1 for D2, if the greatest common divisor gcd(U1, U2)=1 for the divisors D1=(U1, V1) and D2=(U2, V2), then the following operation is performed.
(3a) ExHarADD3+1→3 
If the greatest common divisor gcd(U1, U2)≠1, then the following exception handling is performed.
(3b) Exception Handling 10
Although algorithms for the respective operations are not explicitly described in published documents, papers, or the like, formulae can be written as described below for the case where field of definition is F2n. That is, algorithms for ExHarADD3+1→3 and ExHarADD3+2→3 are shown below in [Table 6] and [Table 7]
[Mathematic Expression 7]
TABLE 6ExHarADD3+1→3 (genus 3)Input: D1 = (u1, v1), deg u1 = 3, D2 = (u2, v2), deg u2 = 1Output: D3 = (u3, v3) = D1 + D21Compute r = res(u1, u2):3Mw0    u202, w1    w0(u + 12 + u20), w2    u20u11, r    w1 + w2 + u10.2Compute inverse of u1 mod u2:1Iinv    1/r.3Compute s0 = inv(v1 + v2) mod u2:3Mz0    w0v12, s0    inv(v10 + v20 + v20v11 + z0).4Compute u3 = (f + hv + v2)/(u1u2), v = s0u1 + v1:12M u32    s02 + s0 + u20 + u12 + f0t0    f6 + s02 + u12, t1    u12t0, t2    u20u32, t3    h2s0,u31    t1 + t2 + t3 + u11 + v12 + f5,t4    u20(t6 + v12 + f5 + t3 + u11), t5    v12(v12 + u12 + h2),t6    u12(u12(f6 + u12) + f5),u30    w0u32 + t4 + t5 + u12t0 + s0h1 + t0 + u10 + f4 + v11,5Compute v3 = v32x2 + v31x + v30 ≡ s0u1 + v1 + h mod u3:3Mv32    v12 + h2 + s0(u12 + u32) + u32:v31    v11 + h2 + s0(u11 + u31) + u31:v30    v10 + h2 + s0(u10 + u30) + u30:totalExHarADD3+1→31I + 21M[Mathematic Expression 8]
TABLE 7ExHarADD1+2→3, ExHarADD1+2→2 (genus 3)Input: D1 = (u1, v1), deg u1 = 3, D2 = (u2, v2), deg u2 = 2Output: D3 = (u3, v3) = D1 + D21Compute r = res(u1, u2):11M w0    u202, w1    u112, w2    u212, w3    u12 + u21.w4    w0(u20 + u12w3), w5    u21(u10 + u11w3), w5    u20(w5 + w1),w6    w3w2 + u21u11, w6    u10(u10 + w6), r    w4 + w5 + w62Compute ru1−1 mod u2 ≡ i1x + i0:4Mi2    u21u12, i3    u21u11, i4    u20u12,i1    i2 + w2 + u20 + u11: i0    w2w3 + i3 + i4 + u103Compute t ≡ t1x + t0 = r(v1 + v2)u1−1) mod u2:7Mc1    v11 + v21 + v12u21, c0    v20 + v10 + v12u20,t2    i1c1, t3    i0c0, t1 = t2u21 + (i1 + i0)(c1 + c0) + t2 + t3,t0    t3 + t2u20.4If t1 = 0 then goto 5′.5Compute s = t/r ≡ s1x + s0:1I + 6Mz1    rt1, z2    1/z1, z3    z2r, z4    z2t1, z5    z3r, s1    z4t1, s0    z4t0.6Compute v = su1 + v1 ≡ s1x4 + k3x3 + k2x2 + k1x + k0:5Mt0    s0u12, t1    s0u10, t2    s1u11,k3    (s1 + s0)(1 + u12) + s1 + t0, k2    t0 + t2 + v12,k1    (s1 + s0)(u11 + u10) + t2 + t1 + v11, k0    t1 + v10.7Compute u3 = s1−2(f + hv + v2)/(u1u2):11M u32    z5(z5 + 1) + u12 + u21, t0    k32, t1    u122,t2    z5(z5(f6 + u12 + u21 + t0 + k3) + u21 + h2 + u12),u31    i2 + u11 + u20 + t1 + w2 + t2,t3    (t1 + w2)(u2l + u12) + i3 + i4 + u10,t4    i2 + u20 + w2 + u11 + t1 + f5 + (u21 + u12)(t0 + f6 + k3) + k2,t4    z5(t4 + k3h2) + h2(u12 + u21) + t1 + w2 + i2 + u20 + u11 + h1, t4    z5t4,u30    t3 + t4.8Compute v3 = v32x2 + v31x + v30 ≡ su1 + v1 + h mod u3:8Mt0    s0(u32 + u12), t1    s1(u31 + u11), t2    s1(u12 + u32).v32    t0 + t1 + t2u32 + u32 = v12 + h2,t4    s0(u30 + u10), t5    (s1 + s0)(u31 + u11 + u30 + u10),v31    t5 + t1 + t4 + t2u31 + u31 + v11 + h1,v30    t4 + t2u30 + u30 + v10 + h0,totalExHarADD3+2→3 1I + 52M5′Compute s = t0/r ≡ s0:1I + 1Ms0    t0/r.6′Compute u3 = x2 + u31x + u30 = (f + hv + v2)/(u1v2):3Mw1    s02, u31    u21 + u12 + w1 + s0,u30    (w1 + u12)(u21 + u12) + (h2 + u21)s0 + w0 + u20 + u11 + v12 + f5.7′Compute v3 = v31x + v30 ≡ s0u1 + v1 + h mod u3:6Mv31    (u30 + u31(u31 + u12) + u11)s0 + u31(u31 + h2 + v12) + u30 + h1 + v11,v30    (u10 + u30(u31 + u12))s0 + u30(u31 + h2 + v12)+ v10 + h0.totalExHarADD3+2→21I + 32M
FIG. 2(B) shows an example of a doubling operation process for genus=3. The doubling operation is an operation to determine D+D=2D. The doubling operation is performed in a different mode depending on which one of values described below is assigned to the weight of the divisor D.
(4) weight=3
(5) weight=2
(6) weight=1
(7) weight=0
(4) When weight=3, it is checked whether the divisor includes a ramification point. If it is determined that the divisor includes no ramification point, then (4a) HarleyDBL is performed. On the other hand, if the divisor includes a ramification point, then (4b) exception process 11 is performed.
In Non-Patent Document 9 or 10, it is described that the process (4a) HarleyDBL occurs most frequently. A specific process of HarleyDBL is shown below in [Table 5].
[Mathematic Expression 9]
TABLE 5HarleyDBL(genus 3)Input: D1 = (u1, v1), deg u1 = 3Output: D3 = (u3, v3) = 2D11Compute r = res(u1, h):15M 2Compute almost inverse inv ≡ r/h mod u1:4M3Compute z = (f + hv1 + v12)/u1 mod u1:12M 4Compute s′ = z · inv mod u1:11M 5Compute s = (s′/r) and make s monic:1I + 8M 6Compute G = su1:6M7Compute u′ = s1−2[(G + w4v1)2 + w4hG + w5(hv1 + f)]:6M8Compute v′ = Gw3 + h + v1 mod u′:8M9Compute u3 = (f + hv + v2)/u′:8M10 Compute v3 = v′ + h mod u3:3MtotalHarleyDBL1I + 81M
The operations of HarleyADD and HarleyDBL for both genus=2 and genus=3 are called most-frequent-case operations, because the probability of occurrence of these operations is very high when addition or doubling is performed for randomly generated divisors. A further detailed description of the fact that the operations of HarleyADD and HarleyDBL occur most frequently may be found, for example, in Non-Patent Document 14.
According to Non-Patent Document 14, the probability of occurrence of operations other than the most-frequent-case operations is O(1/q) where q is the number of elements of the field of definition. In practical use of cryptography that provides a reasonably high security level, qg is as large as a value representable by about 160 bits, and thus only HarleyADD or HarleyDBL occurs in practical operations.
Therefore, in many cases, when the addition algorithm of the hyperelliptic curve cryptography (HECC) is implemented using the Harley algorithm or a modification thereto in cryptographic processing means such as an IC card, only
HarleyADD and
HarleyDBL
are implemented, and the other exceptional operations which hardly occur are not performed. In this case, the exceptional operations may be performed, for example, in accordance an algorithm such as a Cantor algorithm which does not need selection of the mode depending on the weight. The processing load for the complicated exceptional operations increases with genus, as discussed in Non-Patent Document 9 or 10.
Scalar multiplication of a divisor according to the hyperelliptic curve cryptography (HECC) algorithm is explained below. In the hyperelliptic curve cryptography (HECC) algorithm, scalar multiplication of a divisor can be accomplished by a combination of hyperelliptic curve addition and hyperelliptic curve doubling. Two typical algorithms of the scalar multiplication are a binary algorithm and a double-and-add-always algorithm.
In the elliptic curve cryptography, as described above, when a point P on an elliptic curve defined over a finite field Fq is given, if a point Q=kP (kεZ), that is, a point obtained by multiplying point P by a scalar k is further given, it is known that a problem of finding k for the given point Q reduces to a discrete logarithm problem. On the other hand, in the case of public key cryptography based on the hyperelliptic curve cryptography, when a divisor D1 which is a formal sum of points and a divisor D2 obtained by multiplying D1 by a scalar k are given, a problem of finding k from D2 reduces to a discrete logarithm problem on a Jacobian variety of a hyperelliptic curve, and this problem can be applied to public key cryptography.
The scalar value d given as the multiplier to be multiplied with the divisor D in the scalar multiplication operation (D=dD) is expressed in a binary form as follows.d=(dl-1, . . . , d0)where dl-1=1, dl-2, . . . , 0=1 or 0.
A basic algorithm of scalar multiplication based on the binary method is described below in [Algorithm 1].
[Mathematic Expression 10]
Binary Method (Algorithm1)Input D0Output D = dD0D    D0for i from l − 2 to 0{D    2D ||HarleyDBL doubling operationif di = 1 then D    D + D0 ||HarleyADD addition operation}return D
Next, a calculation algorithm based on the double-and-add-always method is described.
A method to know secret information by attacking a weak point of implementation of a cryptography technique is called side channel attack (SCA). Specific examples of SCA include timing attack (TA), simple power analysis (SPA), and differential power analysis (DPA). In the SCA, an attack is made by detecting a processing time of a process having a correlation to secret information. In power attach such as the SPA or DPA, an attack is made by detecting a correlation between secret information and power consumption. A further detailed description of the timing attach (TA) may be found, for example, in Non-Patent Document 15, and that of the power attack may be found, for example, in Non-Patent Document 16.
In the simple power analysis (SPA), secret information is revealed by directly detecting a waveform of power consumption dependent on bit information of a secret key. To enhance resistance of the cryptography algorithm against attack by the SPA, it is needed that the algorithm do not produce a correlation between bit information of the secret key and the power waveform. On the other hand, to increase resistance to the timing attack (TA), it is needed that the algorithm do not produce a correlation between bit information of the secret key and the processing time.
It is known that the double-and-add-always method can provide high resistance against the timing attack (TA) or the power attack (SPA) to the elliptic curve cryptography (ECC) or the hyperelliptic curve cryptography (HECC). A further detailed description of the resistance of the double-and-add-always method against the attack can be found in the Non-Patent Document 17. In the double-and-add-always algorithm, unlike the binary algorithm described above, a dummy addition is always performed so that the processing time or the power waveform does not vary depending on the bit value of the scalar multiplier d.
A basic algorithm of scalar multiplication based on the double-and-add-always method is described below in [Algorithm 2].
[Mathematic Expression 11]
Double-and-add-always Method (Algorithm2)Input D0Output D = dD0D[0]    D0for i from l − 2 to 0{D[0]    2D[0] ||HarleyDBL doubling operationD[1]    D[0] + D0 ||HarleyADD addition operationD[0]    D[di]}return D[0]
Next, a process of producing a base point is described below. When scalar multiplication is used in cryptography, an input divisor D0 can be categorized into two types:
(1) predetermined divisors
(2) unpredictable divisors which occur randomly
When an input divisor is of the type (1), that is, a predetermined divisor, the input divisor is called a base point.
A general algorithm of producing a base point is described below.
(a)
First, g elements on the field of definition Fq are selected at random, and g points Pi (i=1, . . . , g) on a hyperelliptic curve are produced.
(a1) Let xi (i=1, . . . , g) denote the x coordinate of each if the elements randomly selected above. The y coordinate which is on the hyperelliptic curve and which corresponds to the x coordinate xi is determined for each element.
(b)
The base point is defined by a divisor D0=(U(x), V(x)) where(b1) U(x)=(x−x1)(x−x2) . . . (x−xg)(b2) V(x)=vg-1xg-1+vg-2xg-2+ . . . +v0 The coefficients vi of V(x)=vg-1xg-1+vg-2xg-2+ . . . +v0 are determined. For example, when there is no duplication in the produced points, vi can be determined from V(xi)=yi.
(c) The divisors produced in the above algorithm have a weight equal to g.
In the case where a predetermined divisor is employed as the divisor D0 used as the base point in the scalar multiplication operation in the cryptographic process, the divisor used as the base point with a weight equal to g can be produced via steps (a) to (c) described above.
[Non-Patent Document 1] N. Koblitz, Hyperelliptic curve cryptosystems”, J. Cryptology, vol. 1, No. 3, pp. 139-150,
[Non-Patent Document 2] D. G. Cantor, Computing in the Jacobian of hyperelliptic curve”, Math. Comp., Vol. 48, No. 177, pp. 95-101, 1987
[Non-Patent Document 3] D. Mumford, Tata lectures on theta II”, Progress in Mathematics, no. 43, Birkhauser, 1984
[Non-Patent Document 4] K. Matsuo, J. Chao, and S. Tsujii, Fast Genus two hyperelliptic curve cryptosystems”, Technical Report ISEC2001-31, IEICE Japan, 2001
[Non-Patent Document 5] Improving Harley algorithms for Jacobians of genus 2 hyperelliptic curves”, SCIS2002 (written in Japanese)
[Patent Document 6] T. Lange, Inversion-free arithmetic on genus 2 hyperelliptic curves”, Cryptology ePrint Archive, 2002/147, IACR, 2002
[Patent Document 7] T. Sugizaki, K. Matsuo, J. Chao, and S. Tsujii, An extension of Harley addition algorithm for hyperelliptic curves over finite fields of characteristic two”, ISEC2002-9, IEICE, 2001
[Patent Document 8] T. Lange, “Efficient arithmetic on genus 2 hyperelliptic curves over finite fields via explicit formulae”, Cryptology ePrint Archive, 2002/121, IACR, 2002
[Patent Document 9] J. Kuroki, M. Gonda, K. Masuo, J. Chao and S. Tsujii, Fast genus three hyperellipitc curve cryptosystems”, SCIS2002
[Patent Document 10] J. Pelzl, T. Wollinger, J. Guajardo, and C. Paar, Hyperelliptic curve Cryptosystems: Closing the Performance Gap to Elliptic Curves”, Cryptology ePrint Archive, 2003/026, IACR, 2003
[Patent Document 11] Y. Miyamoto, H. Doi, K. Matsuo, J. Chao and S. Tsujii, A fast addition algorithm of genus two hyperelliptic curves”, SCIS2002 (written in Japanese)
[Patent Document 12] N. Takahashi, H. Morimoto and A. Miyaji, Efficient exponentiation on genus two hyperelliptic curves (II)”, ISEC2002-145, IEICE, 2003 (written in Japanese)
[Patent Document 13] T. Lange, Weighed coordinate on genus 2 hyperellipitc curve”, Cryptology ePrint Archive, 2002/153, IACR, 2002
[Patent Document 14] N. Nagao, Improving group law algorithms for Jacobians of hyperelliptic curves”, ANTS-IV, LNCS 1838, pp. 439-448, Springer-Verlag, 2000
[Patent Document 15] C. Kocher, “Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems”, CRYPTO '96, LNCS 1109, pp. 104-113, 1996
[Patent Document 16] C. Kocher, J. Jaffe, and B. Jun, “Differential Power Analysis”, CRYPTO '99, LNCS 1666, pp. 388-397, Springer-Verlag, 1999
[Patent Document 17] J.-S. Coron, “Resistance against Differential Power Analysis for Elliptic Curve Cryptosystems”, CHES '99, LNCS 1717, pp. 292-302, Springer-Verlag, 1999